/**
 * 分割回文串 2
 *
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
 * 返回符合要求的 最少分割次数 。
 *
 * 示例 1：
 * 输入：s = "aab"
 * 输出：1
 * 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
 *
 * 示例 2：
 * 输入：s = "a"
 * 输出：0
 *
 * 示例 3：
 * 输入：s = "ab"
 * 输出：1
 *
 * 提示：
 * 1 <= s.length <= 2000
 * s 仅由小写英文字母组成
 */

/**
 * 这题我们使用两个 dp 来解决
 * dp1[i][j] : s 的 i, j位置是否是回文串
 * 这个就不用多解释了
 * dp2[i] : s 的 i 位置最少需要分割多少次才能使每一个子串都为回文串
 * 这里有两种情况, 1 : dp1[0][i] 为 true, 那么就不需要分割了, dp2[i] = 0;
 *              2 : dp1[0][i] 为 false, 那么我们就需要借助前面算出来的 dp2 来解决问题了
 *                  从 0 再遍历一遍到 i, 要是遇到 dp1[j][i] 为 true, 就借助 dp2[j - 1] 来
 *                  求 dp2[i], 这样遍历到 i 位置, 更新最小值, 这种情况下为了避免原来的 dp2[i]
 *                  中的值造成影响, 我们初始化为 max, 这里就是最差情况, 需要分割 i 次
 *                  这里注意不是 i - 1 次, 因为 i - 1 对应的是下标, i 才是最多的次数
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {
    public int minCut(String s) {

        // 长度
        int n = s.length();

        // 判断是否为回文串
        boolean[][] dp1 = new boolean[n][n];

        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {

                // 这里 right 和 left 都是从 0 开始, 没有关系, 因为我们的条件会很好的解决这些问题
                if (s.charAt(left) == s.charAt(right)
                        && (right - left <= 2 || dp1[left + 1][right - 1])) {
                    dp1[left][right] = true;
                }
            }
        }

        // 次数
        int[] dp2 = new int[n];

        // 这里 i j 从头开始也没有关系, 因为上面的从头开始帮我们初始化好了所有的情况
        for (int i = 0; i < n; i++) {

            if (dp1[0][i]) {

                // 第一种情况
                dp2[i] = 0;
            } else {

                // 第二种情况, 我们先初始化为 i(最大分割次数)
                dp2[i] = i;

                for (int j = 0; j <= i; j++) {

                    // 寻找前面的回文串, 要是没有, 就是最大次数
                    if (dp1[j][i]) {

                        // 查找前面的最小值
                        dp2[i] = Math.min(dp2[i], dp2[j - 1] + 1);
                    }
                }
            }
        }

        // 返回值
        return dp2[n - 1];
    }
}